<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Repairing Conflicts
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial093.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial095.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc184">13.3</A>&nbsp;&nbsp;Repairing Conflicts</H2><UL>
<LI><A HREF="tutorial094.html#toc92">Combining Repair with IC Propagation</A>
</UL>

<A NAME="@default346"></A>
If all the constraints of a problem are monitored for conflicts, then
the problem can be solved by: 
<UL CLASS="itemize"><LI CLASS="li-itemize">
Finding an initial assignment of tentative values for all the problem
variables
<LI CLASS="li-itemize">Finding a constraint in conflict, and labelling a variable in this
constraint
<LI CLASS="li-itemize">Instantiating the remaining variables to their tentative values, when
there are no more constraints in conflict
</UL>
Consider a satisfiability problem with each clause represented by an
<TT>ic</TT> constraint, whose form is illustrated by the following example: 
<CODE>(X1 or neg X2 or X3 $= 1</CODE>.
This represents the clause <I>X</I>1 &or; &not; <I>X</I>2 &or; <I>X</I>3.<BR>
<BR>
To apply conflict minimisation to this problem use the predicate:
<UL CLASS="itemize"><LI CLASS="li-itemize">
<CODE>tent_init</CODE> to find an initial solution 
<LI CLASS="li-itemize"><CODE>conflict_constraints</CODE> and <CODE>term_variables</CODE> to find a
variable to label
<LI CLASS="li-itemize"><CODE>set_to_tent</CODE> to set the remaining variables to their
tentative values
</UL>
The code is as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
prop_sat_1(Vars) :-
    Vars = [X1,X2,X3],
    tent_init(Vars),
    (X1 or neg X2 or X3 $= 1) r_conflict cs,
    (neg X1 or neg X2 $= 1) r_conflict cs,
    (X2 or neg X3 $= 1) r_conflict cs,
    min_conflicts(Vars).

tent_init(List) :-
    ( foreach(Var,List) do Var tent_set 1 ).

min_conflicts(Vars) :-
    conflict_constraints(cs,List), 
    ( List = [] -&gt; set_to_tent(Vars) ;
      List = [Constraint|_] -&gt;
        term_variables(Constraint,[Var|_]),
        guess(Var),
        min_conflicts(Vars)
    ).

guess(0).
guess(1).

set_to_tent(Term) :-
   Term tent_get Tent,
   Term = Tent.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The value choice predicate <CODE>guess</CODE> is naive. Since the variable
occurs in a conflict constraint it would arguably be better to label
it to another value. This would be implemented as follows:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
guess(Var) :-
    Var tent_get Value,
    ( Value = 0 -&gt; (Var=1 ; Var=0) 
    ; Value = 1 -&gt; (Var=0 ; Var=1)
    ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<A NAME="toc92"></A>
<H3 CLASS="subsection"><A NAME="htoc185">13.3.1</A>&nbsp;&nbsp;Combining Repair with IC Propagation</H3>
To illustrate a combination of <TT>repair</TT> with <TT>ic</TT> propagation
we tackle a scheduling example.
The problem involves tasks with unknown start times, and known
durations, which are related by a
variety of temporal constraints.
These temporal constraints are handled, for the purposes of this
example, by <TT>ic</TT>.
The temporal constraints are encoded thus:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
before(TimePoint1,Interval,TimePoint2) :-
    TimePoint1+Interval #=&lt; TimePoint2.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<CODE>TimePoint1</CODE> and <CODE>TimePoint2</CODE> are variables (or numbers),
but we assume, for this example, that the
<CODE>Interval</CODE> is a number. 
This constraint can enforce a minimum separation between start times,
or a maximum separation (if the <CODE>Interval</CODE> is negative). It can
also enforce constraints between end times, by adjusting the
<CODE>Interval</CODE> to account for the task durations.<BR>
<BR>
Additionally we assume that certain tasks require the same resource and
cannot therefore proceed at the same time. The resource
constraint is encoded thus:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
noclash(Start1,Duration1,Start2,_) :-
    Start2 #&gt;= Start1+Duration1.
noclash(Start1,_,Start2,Duration2) :-
    Start1 #&gt;= Start2+Duration2.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Suppose the requirement is to complete the schedule as early as
possible.
To express this we introduce a last time point <CODE>End</CODE> which is
constrained to come after all the tasks.
Ignoring the resource constraints, the temporal constraints are easily
handled by <TT>ic</TT>.
The optimal solution is obtained simply by posting the temporal
constraints and then instantiating each start
time to the lowest value in its domain.<BR>
<BR>
To deal with the resource constraints conflict minimisation is used.
The least (i.e. optimal) value in the domain of each variable is
chosen as its tentative value, at each node of the search tree.<BR>
<BR>
To fix a constraint in conflict, we simply invoke its nondetermistic
definition, and 
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> then unfolds the first clause and sends the new temporal
constraint <CODE>Start2 #&gt;= Start1+Duration1</CODE> to <TT>ic</TT>.
On backtracking, the second clause will be unfolded instead.<BR>
<BR>
After fixing a resource constraint, and posting a new temporal
constraint, <TT>ic</TT> propagation takes place, and then the tentative
values are changed to the new <TT>ic</TT> lower bounds.<BR>
<BR>
The code is simply this:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic), lib(repair), lib(branch_and_bound).
schedule(Starts,End) :-
    Starts = [S1,S2,...,End],
    Starts :: 0..1000,
    before(S2,5,S1),
    before(S1,8,End),
    ...
    noclash(S1,4,S2,8) r_conflict resource_cons,
    ...
    minimize(repair_ic(Starts),End).

repair_ic(Starts) :-
    set_tent_to_min(Starts),
    conflict_constraints(resource_cons,List),
    ( List = [] -&gt; 
        set_to_tent(Starts)
    ; List = [Constraint|_] -&gt;
        call(Constraint),
        repair_ic(Starts)
    ).

set_tent_to_min(Vars) :-
    (  foreach(Var,Vars) 
    do 
         get_min(Var,Min),
         Var tent_set Min
    ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
This code is much more robust than the traditional code
for solving the bridge scheduling example from [<A HREF="tutorial133.html#VanHentenryck"><CITE>27</CITE></A>].
The code is in the examples directory file <CODE>bridge_repair.pl</CODE>.<BR>
<BR>
<A NAME="@default347"></A>
This algorithm uses the <TT>ic</TT> solver to:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Enforce the consistency of the temporal constraints
<LI CLASS="li-itemize">Set the tentative values to an optimal solution (of this
relaxation of the original problem)
</UL> 
This technique is called <EM>probing</EM>.
The use of the <TT>eplex</TT> solver, instead of <TT>ic</TT> for probing is
described in 
chapter <A HREF="tutorial121.html#chaphybrid">17</A> below.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	Repair naturally supports conflict
minimisation.
This algorithm can be combined with other solvers, such as <TT>ic</TT>,
and with optimization.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 13.3: Conflict Minimisation</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial093.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial095.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
